1. Field of the Invention
The present invention relates generally to memory devices, and more particularly to a content addressable memory device for providing uninterrupted search operations synchronized with read/write operations and independent search and maintenance interfaces.
2. Description of the Related Art
Memory devices are indispensable components of modem computer systems. As storage devices, they are used to provide fast access to data and instructions stored therein. Content addressable memory (CAM) is a special type of memory that is often used for performing address searches. For example, Internet routers often include a CAM for searching the address of specified data. The use of CAMs allows the routers to perform address searches to allow computer systems to communicate data with one another over networks. Besides routers, CAMs are also utilized in other areas such as database searches, image processing, and voice recognition applications.
CAMs generally include a two-dimensional row and column content address memory array of core cells, such that each row contains an address, pointer, or bit pattern entry. Based on such array of cells, a CAM may perform xe2x80x9creadxe2x80x9d and xe2x80x9cwritexe2x80x9d operations at specific addresses like a conventional random access memory (RAM). In addition, it also performs xe2x80x9csearchxe2x80x9d operations that simultaneously compare a bit pattern of data known as xe2x80x9ccomparandxe2x80x9d against an entire list (i.e., column) of pre-stored entries (i.e., rows) of bit patterns in the CAM array.
Conventional CAMs are typically two port devices. FIG. 1A shows a block diagram of a conventional two-port CAM 100. The CAM 100 includes an input port 107 and an output port 109. The input port 107 communicates data and control signals over a data bus 102 for communicating data and an instruction bus 104 for transmitting instructions associated with an operation to be performed. The data bus 102 is used to receive a comparand or write data as inputs and is thus shared for performing either a search operation or a write operation.
The output port 109 is shared for a search operation or a read operation. Specifically, the output port 109 outputs either search results or read results from the CAM 100 via an output bus 106. In a search operation, for example, the CAM 100 may output a search result, via output bus 106, in the form of an address, pointer, or bit pattern corresponding to an entry that matches the input data. Alternatively, the read results may be output through the data bus 102.
The conventional CAM 100 typically performs operations such as search, read, and/or write operations in sequence. FIG. 1B shows an exemplary sequence of operations that are serially performed in successive memory clock cycles by the CAM 100. As shown in FIG. 1B, the CAM performs a series of operations beginning with three xe2x80x9csearchxe2x80x9d operations, a xe2x80x9cwritexe2x80x9d operation, two xe2x80x9csearchxe2x80x9d operations, a xe2x80x9cwritexe2x80x9d operation, two xe2x80x9creadxe2x80x9d operations, and ending with two xe2x80x9csearchxe2x80x9d operations. These operations are performed one after another, in sequence, with each operation being performed in at least one clock cycle.
Unfortunately, however, the sequential nature of the CAM operations degrade the performance of a CAM by delaying search operations. This is because the xe2x80x9creadxe2x80x9d and xe2x80x9cwritexe2x80x9d operations interrupt xe2x80x9csearchxe2x80x9d operations. As can be appreciated, the interruption in such search operations presents a significant impediment to high speed xe2x80x9creal timexe2x80x9d successive address searching and thereby complicates system design. For example, Internet routers are often called upon to perform many searches of routing tables stored in their CAMs. In such situations, interruptions in searches delay the processing of search operations and thus slow down the response times of computer systems in general.
Additionally, the sharing of the input port 107 by comparand and write data typically requires multiplexing of comparand and write data for input to the CAM 100 Similarly, the sharing of the output port 109 for outputting search results and read results also entails de-multiplexing these results. FIG. 1C shows a more detailed block diagram of the conventional two-port CAM 100 with a multiplexer 111 and a de-multiplexer 113. The CAM 100 includes a control block 108 and a CAM array 110. The multiplexer 111 receives a comparand and/or write data as inputs and selects either the comparand or the write data for output in response to a control signal. The selected output from the multiplexer 111 is then provided to the data bus 102 for input to the CAM array 110.
To control the operation of the CAM 100, control signals are provided to the instruction bus 104 for input to the control block 108. In response to the control signals, the control block 108 generates another set of control signals for controlling the operations of the CAM array 110. In a search operation, the CAM array 110 outputs, on the result bus 106 an address, pointer, or bit pattern (collectively referred herein as xe2x80x9caddressxe2x80x9d) corresponding to an entry or word in the CAM array 110 that matches the input data on the data bus 102. For a read operation, on the other hand, the CAM outputs on the result bus 106 data corresponding to the address provided on data bus 102.
The demultiplexer 113 is coupled to receive an output result from the output bus 106 as an input. When the CAM operation is a search operation, the demultiplexer 113 routes the output result onto a search data bus 115. On the other hand, when the CAM operation is a read operation, the demultiplexer 113 routes the output result onto a read data bus 117.
FIG. 1D shows another block diagram of the conventional CAM 100 in more detail. The CAM 100 includes data bus 102, instruction bus 104, result bus 106, control block 108, CAM array 110, multiplexer (MUX) 112, comparand register 114, global mask registers 116, status register 118, and address counter 120. The control block 108 receives instructions for a desired operation through instruction bus 104, and generates the control signals for the xe2x80x9csearch,xe2x80x9d xe2x80x9cread,xe2x80x9d and xe2x80x9cwritexe2x80x9d operations of the CAM array 110. The CAM 100 illustrated in FIG. 1D is commercially available, for example, as model NL85721 Ternary Content Addressable Memory IPCAM from Netlogic Micosystems, Inc.
Unfortunately, using a multiplexing scheme in performing read/write and search operations adds complexity in implementing conventional two-port CAMs with attendant increase in cost. Furthermore, the multiplexing scheme slows down overall CAM performance since read/write data cannot be input or output simultaneously in a same clock cycle with a search data or result. Indeed, a read or write operation must xe2x80x9cstealxe2x80x9d cycles from the search operations because the buses 102 and 106 are shared.
In view of the foregoing, there is a need for a CAM device and method that can perform read/write operations and search operations simultaneously without multiplexing input data and output results so as to improve CAM performance.
The present invention fills this need by providing three-port content addressable memory (CAM) devices and methods for implementing the same. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, or a method. Several embodiments of the present invention are described below.
In one embodiment, the present invention provides a three-port CAM device including a CAM, a search control block, and a maintenance control block. The CAM is configured to store data. The search control block is arranged to receive search data and search control signals via a first port for searching the search data in the CAM. The search control block is further configured to perform search operations by accessing the CAM. The search operations are performed within search cycles with each search operation being performed over multiple clock cycles. In this configuration, more than one search operations are capable of being performed simultaneously over one or more clock cycles. Search results of the search operations are output via a second port. The maintenance control block is configured to perform read/write operations by reading or writing specified data in the CAM via a third port.
In another embodiment, the present invention provides a method for performing search operations and read/write operations in a CAM device. In this method, a CAM is provided for storing data. Search data and search control signals are then provided to a search control block via a first port for searching the search data in the CAM. The search control block is configured to perform search operations by accessing the content addressable memory. The search operations are performed within search cycles over multiple clock cycles. More than one search operations are capable of being performed simultaneously over one or more clock cycles. Search results from the CAM are output via a second port. Read/write operations are performed by reading or writing specified data in the CAM via a third port.
In yet another embodiment, a three-port CAM device for accessing a CAM containing data is disclosed. The three-port CAM device includes a content addressable memory for storing data, a first port, a second port, and a third port. The first port is configured to receive search data and search control signals for searching the search data in the content addressable memory. Search operations are performed by accessing the content addressable memory. The second port is configured to output search results from the content addressable memory. The third port is configured to communicate read/write data to and from the content addressable memory for read/write operations.
Advantageously, the three-port arrangement of the present invention effectively separates search datapath and read/write datapath. This allows read/write operations to be performed during search clock cycles without corrupting or otherwise compromising the search results. Furthermore, allowing a read/write operation to be performed in a search cycle speeds up search operations by eliminating search interruptions caused by read/write operations. Accordingly, the devices and method of the present invention provide a faster speed of operation at a given clock frequency. Other advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.